import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    public boolean isPail (ListNode head) {
        // write code here
        //先找到中间链表的结点

        if(head==null||head.next==null){
            return true;
        }

        ListNode fast=head;
        ListNode slow=head;

        while(fast!=null&&fast.next!=null){
            //让fast停留在最后一个结点
            slow=slow.next;
            fast=fast.next.next;

        }
        //最后快指针停留在最后一个结点，慢指针停留在中间结点

        //从中间开始反转
        ListNode cur=slow;
        ListNode prev=null;

        while(cur!=null){
            ListNode temp=cur.next;
            cur.next=prev;
            prev=cur;
            cur=temp;
        }
        //反转完成之后prev停留在最后一个结点位置

        while(prev!=null){
            if(head.val!=prev.val){
                return false;
            }
            head=head.next;
            prev=prev.next;
        }
        return true;
    }
}